package com.cat.graphTheory;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/minimum-cost-path-with-edge-reversals/
 * @create 2025/9/24 19:29
 * @since JDK17
 */

public class Solution30 {
    public int minCost(int n, int[][] edges) {
        List<int[]>[] g = new List[n];
        Arrays.setAll(g, i -> new ArrayList<>());
        for (int[] e : edges) {
            g[e[0]].add(new int[]{e[1], e[2]});
            g[e[1]].add(new int[]{e[0], e[2] * 2});
        }
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        int[] dis = new int[n];
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[0] = 0;
        heap.add(new int[]{0, 0});
        while (!heap.isEmpty()) {
            var u = heap.poll();
            int cur = u[0];
            int cost = u[1];
            if (cost > dis[cur]) {
                continue;
            }
            if (cur == n - 1) {
                return cost;
            }
            for (var v : g[u[0]]) {
                if (cost + v[1] < dis[v[0]]) {
                    dis[v[0]] = cost + v[1];
                    heap.add(new int[]{v[0], dis[v[0]]});
                }
            }
        }
        return -1;
    }
}
